package reda.trees;



import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;

public class BST{
	
	
	
	/**
	 * Insert new element in the binary search Tree
	 * @param root
	 * @param value
	 */
	public void insert(Node root, int value){
		if (value < root.value)
			if (root.left != null)
				insert(root.left, value);
			else
				root.left = new Node (value);
		
		else
			if (root.right != null)
				insert(root.right, value);
			else
				root.right = new Node (value);
		
	}

	/**
	 * Get the depth of the binary Tree
	 * @param root
	 * @return
	 */
	public int getMaxLevel(Node root){
		
		if (root==null)
			return 0;				
		return 1+Math.max(getMaxLevel(root.right), getMaxLevel(root.left));
	}
	/**
	 * Print the diagram of the Tree
	 * @param root
	 */
	public void printTreeDiagram(Node root){
		BSTPrinter printer = new BSTPrinter();
		ArrayList<Integer> printArr = printer.getDetailledArray(root);
		printer.printFromArray(root, printArr);
	}

	/**
	 * Breadth First traversal
	 */
	public void breadthTraversal(Node root){
		Queue<Node> queue = new LinkedList<Node>() ;
	    if (root == null)
	        return;
	    queue.clear();
	    queue.add(root);
	    while(!queue.isEmpty()){
	        Node node = queue.remove();
	        System.out.print(node.value + " ");
	        if(node.left != null) queue.add(node.left);
	        if(node.right != null) queue.add(node.right);
	    }
	}
	/**
	 * Print by levels 
	 */
	
	public void printByLevels(Node root){
		
		//Queues utils
		Queue<Node> queue = new LinkedList<Node>();
		Queue<Integer> levelQueue = new LinkedList<Integer>();
		Queue<Integer> orderQueue = new LinkedList<Integer>();
		//A special node is inserted when null
		Node specialNode = new Node(-300);
		if (root == null)
			return;
		
		//Init
		queue.clear();
		levelQueue.clear();
		orderQueue.clear();
		
		int maxLevel = getMaxLevel(root);
		
		int previousLevel = -1;
		int previousOrder = 0;
		Integer level = -1;
		//Add first elments
		queue.add(root);
		levelQueue.add(0);
		orderQueue.add(1);
	
		while (!queue.isEmpty() && level < 5) {
			Node node = queue.remove();
			level = levelQueue.remove();
			Integer order = orderQueue.remove();
			// previousOrder = order;
			if (previousLevel < level) {
				// if(node.value != -300){
				//System.out.println("*******level= " + level);
				 System.out.println();
				// }
				previousOrder = 0;
			}
			//-----------------------------------------------------------------------------
			int i=0;
			if(order ==1){
				//while( i<maxLevel-level){
				while(i<getLeftSpace(level, maxLevel)){
					System.out.print(" ");
					i++;
				}
			}else{
				 i=0;
				while(i<getLeftSpace(level-1, maxLevel)){
					System.out.print(" ");
					i++;
				}
			}
			
			
			if (node.value != -300) {
				
				System.out.print(node.value+" ");
				//System.out.print(node.value + " order= " + order);
			}else{
				System.out.print("- ");
			}
			
			
			
			//--------------------------------------------------------------------------------
			previousLevel = level;
			// ----------------------------------------------------------------------
			previousOrder++;
			// for left
			if (node.left != null) {
				queue.add(node.left);
				levelQueue.add(level + 1);
				orderQueue.add(previousOrder);
			} else {
				queue.add(specialNode);
				levelQueue.add(level + 1);
				orderQueue.add(previousOrder);
			}
			// -----------------------------------------------------------------------
			previousOrder++;
			if (node.right != null) {
				queue.add(node.right);
				levelQueue.add(level + 1);
				orderQueue.add(previousOrder);
			} else {
				queue.add(specialNode);
				levelQueue.add(level + 1);
				orderQueue.add(previousOrder);
			}
		}
	}

	private int getLeftSpace(int currLevel, int maxHeight ){
		int n = maxHeight - currLevel;
		if (n<=1)
			return 1;
		int sum = 1;
		for(int i= 1; i<n;i++)
			sum += Math.pow(2, i);
		return sum;	
	}
	
	/**
	 * Depth First Traversal
	 */
	
	public void depthTraversal(Node root){
		
	}
	/**
	 * Balance the binary Tree
	 * @param root
	 */
	
	public void balance(Node root){
		
	}

	/**
	 * Insert a new element and keep Tree Balanced
	 * @param root
	 * @param value
	 */
	public void insertBalanced(Node root, int value){
		//TODO
	}
	
	


}
